/*
 * @Author: 缄默
 * @Date: 2021-10-27 15:35:04
 * @LastEditors: 缄默
 * @LastEditTime: 2021-10-27 16:07:27
 */

//将搜索二叉树转换成双向链表

//写本题主要是为了熟悉容器的操作，了解一下队列的用法

#include <iostream>
#include <queue>

using namespace std;



struct ListNode {
    int value;
    ListNode* next;
    ListNode* last;
    ListNode(int x) : value(x), next(nullptr), last(nullptr) { }
    ListNode() : value(0), next(nullptr), last(nullptr) { }
    
};

int main() {
    queue<int> Que({1, 2 , 3, 4, 5});
    ListNode* head = new ListNode(Que.front());
    head->last = nullptr;
    ListNode* cur = head;
    ListNode* last = head;
    Que.pop();
    while (!Que.empty()) {
    cur->next = new ListNode(Que.front());
    Que.pop();
    last = cur;
    cur = cur->next;
    cur->last = last;
    }
    cur->next = nullptr;
    last = cur;
    cout << "正序" << endl;
    cur = head;
    while (cur != nullptr) {
        cout << cur->value << endl;
        cur = cur->next;
    }
    cur = last;
    cout << "逆序" << endl;
    while (cur != nullptr) {
        cout << cur->value << endl;
        cur = cur->last;
    }
    return 0;
}


